Problem statement: zenit13ckc
| C: Age of Empires |
| 20 bodov | Časový limit: 100 ms |
Age of Empires je klasická strategická hra z roku 1997, v ktorej ťažíte suroviny, staviate budovy,
trénujete vojenské jednotky a bojujete so súperom. Odohráva sa v staroveku, ktorý je rozdelený na
štyri doby - Stone Age, Tool Age, Bronze Age a Iron Age. Prechod z doby do nasledujúcej je drahý, ale
prináša veľké množstvo nových bojových jednotiek a technológií.
Civilizácia Chetitov sa nedávno dostala do Tool Age, vynašla stenu a poď ho nadšene stavať ochranu
svojho malého, ale o to intenzívnejšie rozrastajúceho sa mesta.
Vodca Chetitov ale zabudol, že dnes bojuje proti Minojcom a tí majú o 30 percent lacnejšie lode.
Netrvalo dlho a okolo pobrežia sa začali obšmietať minojské bojové lode z doby bronzovej, ktoré sú oveľa
silnejšie ako tie, ktoré môžu stavať Chetiti vo svojej súčasnej dobe. Neostáva im teda nič iné ako poraziť
nepriateľa početnou presilou. Koľko slabších lodí treba na zničenie jednej silnejšej?
Bojové lode po sebe strieľajú šípy. V tomto zadaní predpokladáme, že všetky lode strieľajú
rovnakou rýchlosťou. Keď sa lode stretnú, zo všetkých naraz vyletí šíp.
Ten vždy zasiahne cieľ a spôsobí škody. Potom nejaký čas trvá, kým sa lode pripravia na nový výstrel
a potom znova naraz všetky vystrelia. V tejto úlohe ignorujeme dostrel - každá zo
zúčastnených lodí dostrelí na každú inú.
Každá loď má nejaký počet hit pointov a nejakú silu útoku (obe sú prirodzené čísla).
Pri zásahu sa od zostávajúceho počtu hit
pointov odpočíta sila útoku strieľajúcej lode. Ak je loď zasiahnutá viacerými útočníkmi, potom sa
samozrejme odpočíta súčet všetkých síl. Ak je počet hit pointov po zásahu nula alebo
záporný, loď sa potápa.
Keď sa stretnú chetitské lode s minojskou, chetitské lode budú ničiť tú minojskú a minojská loď bude
postupne po jednom ničiť chetiské lode - keď nejakú začne ničiť, tak do nej strieľa, až kým sa nepotopí.
Všetky lode majú na začiatku plný počet hit pointov.
Prečítajte zo vstupu štyri čísla h1, s1, h2, s2 - hit pointy a silu slabšej (chetitskej) lode a hit
pointy a silu silnejšej (minojskej) lode. Môžete predpokladať, že 1 ≤ h1 ≤ h2 ≤ 2,000,000,000 a
1 ≤ s1 ≤ s2 ≤ 2,000,000,000. Na výstup vypíšte najmenší počet slabších lodí,
ktoré sú schopné zničiť jednu silnejšiu. V prípade, že sa minojská loď potopí súčasne s poslednou chetitskou, je to postačujúce.
>
Príklady:
Silnejšia loď potrebuje 15 výstrelov na zničenie slabšej. Jedna slabšia loď nestačí, silnejšia loď prežije
s 85 hit pointami (160 - 15·5). Keď sa silná loď stretne s dvoma slabšími, tak po
15 výstreloch potopí prvú, ale jej samej v danej chvíli zostane už len 10 hit pointov.
Po ďalších dvoch výstreloch sa potopí. Druhej slabšej lodi zostane 104 hit pointov.
Silná loď potrebuje 10 výstrelov na zničenie slabšej. Ak sa stretne jedna silná a jedna slabá, tak silná prežije
so 150 hit pointami. Ak sa stretne jedna silná s dvoma slabšími, tak po zničení prvej jej zostane 100
hitpointov a po zničení druhej 50. Stret s troma slabšími už nevydrží. Prvá slabá padne, druhej ostane
60 hit pointov a tretia zostane nedotknutá.
